\documentclass[10pt]{amsart}

\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{tikz}
\usepackage[all]{xy}

\renewcommand{\familydefault}{\sfdefault}
\setlength\parindent{0cm}

\DeclareMathOperator{\ord}{ord}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Prob}{Prob}

\title{Theorem 4.7}
\date{}

\begin{document}
\maketitle

\subsection*{Definition}
A \emph{tangle} is a connected $\Pi$-labelled graph $\Psi$ which is potentially contained in some element of $\mathcal{G}_{n,d}$ where here by \emph{contained} we mean that there is an inclusion of graph which preserves the $\Pi$-labelling.

\subsection*{Statement}
Let $\Psi$ be a loopy tangle (that is of non-negative order, or equivalently, not a tree) then the expected number of occurrences of that tangle in an element $G$ of $G_{n,d}$ is $n^{-r}+O(n^{-r-1})$ and the probability that it occurs at least once is
\[
\frac{1}{cn^r} - \frac{1}{2c^2n^{2r}} + O\!\!\left(\frac{1}{n^{r+1}}\right) \quad \text{or simply} \quad \frac{1}{cn^r} + O\!\!\left(\frac{1}{n^{r+1}}\right)
\]
where $c=|\Aut(\text{Pruned}(\Psi))|$ is the number of automorphisms of the complete pruning of the graph $\Psi$ and $r=\ord(\Psi)$ is its order.

\subsection*{Comments}
It seems that this statement actually depends on the graph $\Psi$ to be equipped with a feasible $\Pi$-labelling and that we're talking about embeddings which preserve this labelling. Same for its automorphisms, which are also $\Pi$-labelled (for example, the triangle has only 3 automorphisms if given a feasible labelling).

\subsection*{Proposition}
Let $\iota: \Psi \hookrightarrow G$ be an embedding of graphs and assume that $G$ is connected. Then the order of $G$ is at least that of $\Psi$.
\begin{proof}
Consider the graph $G_\iota$ which is the graph obtained by identifying all the vertices of $\iota(\Psi)$ and removing all the edges in $\iota(E_\Psi)$, in other words $G_\iota$ is the quotient of $G$ by the embedding $\iota$. By construction we have
\[
|V_G| = |V_\Psi| + |V_{G_\iota}| + 1 \quad\text{and}\quad |E_G| = |E_\Psi| + |E_{G_\iota}|
\]
And hence
\[
\ord(G) = \ord(\Psi) + \ord(G_\iota) +1 \geq \ord(\Psi)
\]
since $G_\iota$ is connected and as such its order is at least -1.
\end{proof}

\subsection*{Proposition}
Let $\iota_1, \iota_2: \Psi \hookrightarrow G$ be two distinct intersecting embeddings of graphs and assume that $\Psi$ is connected and completely pruned and $G$ is connected. Then the order of $G$ is strictly greater than that of $\Psi$.
\begin{proof}
Without loss of generality, we can assume that $G = \iota_1(\Psi) \cup \iota_2(\Psi)$. A graph which is pruned and connected is either a cycle or is 1-loopy.\\

If $\Psi$ is a cycle, then there must exist at least one edge $e$ which belongs to $G \,\backslash \iota_1(\Psi)$ and which leaves $G \,\backslash \{ e \}$ connected. Hence $\iota_1: \Psi \hookrightarrow G \,\backslash \{ e \}$ is an embedding of connected graphs and by the previous proposition
\[
\ord(\Psi) \leq \ord(G \,\backslash \{ e \}) = \ord(G) -1 < \ord(G)
\]

If $\Psi$ is 1-loopy, we can also find an edge which is not a cut-edge of $G$ to remove and that preserves at least one of the embeddings. If $e$ is any edge in $E_G \,\backslash E_{\iota_1(\Psi)}$, removing it will preserve the embedding $\iota_1$, the only problem is whether is is a cut-edge. If it is a cut-edge, then the connected component of $G \,\backslash \{ e \}$ which doesn't contain $\iota_1(\Psi)$ must be loopy and hence contains an edge on an irreducible closed loop that we could remove instead of $e$ and using the same argument as above, the order of $\Psi$ is strictly less than that of $G$.
\end{proof}

\subsection*{Proposition}
Let $\Psi$ be a $\Pi$-labelled graph and let $\Psi'$ be a $\Pi$-labelled graph whose complete pruning is the graph $\Psi$, then the probability that the graph $\Psi'$ occurs in random element of $\mathcal{G}_{n,d}$ is $1+O(n^{-1})$ times the probability that $\Psi$ occurs. In other words, as $n$ tends to infinity, the probability that a $\Pi$-labelled graph occurs is the probability that its complete pruning occurs.
\begin{proof}
We can construct $\Psi'$ from the graph $\Psi$ by adding each pruned edge one at a time. For each edge, the probability that it occurs as a free edge (and not as a loop or as an edge connecting to an original vertex of the graph) is
\[
\frac{n-c_1}{n-c_2} = 1+O\!\left(\frac{1}{n}\right) \quad\text{with } c_2<c_1
\]
Where $c_1$ is the number of vertices of the graph (not counting the vertex that will be added when the pruned edge is added) and $c_2$ is the number of values of the permutation corresponding to the pruned edge which have already been assigned. And since $(1+O(n^{-1}))^k=1+O(n^{-1})$ we obtain that adding pruned edges doesn't change much the probability of the occurrence as $n$ gets larger.
\end{proof}

\subsection*{Detailed proof of the statement}
Considering the above proposition, we can assume that the tangle $\Psi$ is completely pruned.\\

The embedding of the tangle $\Psi$ into an element $G$ of $G_{n,d}$ is completely described by the map on the vertices (since we have a $\Pi$-labelling). We will study all possible assignments of the vertices of the graph $\Psi$ into $G$. Such an assignment can be described by a $k$-tuple $\vec{m}$ of distinct integers between 1 and $n$ (where $k$ is the number of vertices of the graph $\Psi$). We denote by $\iota_{\vec{m}}$ the map from the vertices of $\Psi$ to $G$ and we denote by $\varepsilon(\vec{m})$ the event that the map $\iota_{\vec{m}}$ is an embedding of $\Psi$ into $G$.

\vspace{1em}

Given a $k$-tuple $\vec{m}$, its associated map $\iota_{\vec{m}}$ on the vertices will be an embedding if for each $\Pi$-labelled edge $\pi_i$ from the vertex $v$ to the vertex $w$ we have that $\pi_i(\iota_{\vec{m}}(v)) = \iota_{\vec{m}}(w)$. In other words, for each edge $\pi_i$ of $\Psi$, we need to fix a value of the permutation $\pi_i$ in order to obtain an embedding. If we denote by $a_i$ the number of edges of the graph $\Psi$ labelled with the permutation $\pi_i$, then the probability that the map $\iota_{\vec{m}}$ is an embedding is
\[
\Prob(\varepsilon(\vec{m})) = \prod_{i=1}^{d/2}\frac{(n-a_i)!}{n!} = n^{-|E_\Psi|} + O(n^{-|E_\Psi|-1})
\]
since the $a_i$ must sum to the number of edges of the graph $\Psi$.

\vspace{1em}

To compute the expected number of occurrences of the tangle $\Psi$ in an element $G$ of the model $G_{n,d}$ we need to count the total number of different possible embeddings. There are $n(n-1)\ldots (n-|V_\Psi|+1) = n^{|V_\Psi|} + O(n^{|V_\Psi|-1})$ ways for the vertices of the graph $\Psi$ to be embedded in the graph $G$, we can conclude that the expected number of embeddings of the graph $\Psi$ into a random graph $G$ on $n$ vertices is $n^{-\ord(\Psi)} + O(n^{-\ord(\Psi)-1})$ since
\begin{align*}
\mathbb{E}(\text{\# of occurrences of $\Psi$ into $G$}) &= \sum_{\vec{m}}\Prob(\varepsilon(\vec{m}))\\
&= \left( n^{|V_\Psi|} + O(n^{|V_\Psi|-1}) \right) \left( n^{-|E_\Psi|} + O(n^{-|E_\Psi|-1}) \right)\\
&= n^{-\ord(\Psi)} + O(n^{-\ord(\Psi)-1})
\end{align*}

In order to compute the probability that the tangle $\Psi$ occurs at least once in the graph $G$, we need to 














\end{document}